/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution92 {

    public static void main(String args[]) {
        Solution92 s = new Solution92();
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        a.next = b;
        b.next = c;
        c.next = d;
        System.out.println(a);
        System.out.println(s.reverseBetween(a, 2, 2));
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode pre = null;
        ListNode end = null;
        int i = 1;
        ListNode cur = head;
        while (cur != null) {
            if (i == m - 1) {
                pre = cur;
            }
            if (i == n + 1) {
                end = cur;
            }
            cur = cur.next;
            i ++;
        }

        if (pre == null) {
            cur = head;
        } else {
            cur = pre.next;
        }
        ListNode l = cur;
        ListNode r = cur.next;
        ListNode t;

        l.next = end;
        while (r != end) {
            t = r.next;
            r.next = l;
            l = r;
            r = t;
        }
        if (pre == null) {
            return l;
        }
        pre.next = l;
        return head;
    }
}
